#include<bits/stdc++.h>

using namespace std;
int c[100000];

void mergeSort(int *a, int left, int right) {
    if (left >= right) return;
    int mid = (right + left) / 2;
    //a[left,mid]  and a[mid+1,right]
    mergeSort(a, left, mid);
    mergeSort(a, mid + 1, right);
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) {
            c[k++] = a[i++];
        } else {
            c[k++] = a[j++];
        }
    }
    while (i <= mid) c[k++] = a[i++];
    while (j <= right) c[k++] = a[j++];
    for (int x = left; x <= right; x++) a[x] = c[x];

}

int main() {
    int a[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
    int n = 10;
    mergeSort(a, 0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }


    return 0;
}